import java.util.Stack;

/**
 * @author jh.pei
 * @date 2024/10/23 13:22
 */
public class 链表相加二 {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        ListNode ln1 = head1;
        ListNode ln2 = head2;
        while (ln1 != null) {
            stack1.push(ln1);
            ln1 = ln1.next;
        }
        while (ln2 != null) {
            stack2.push(ln2);
            ln2 = ln2.next;
        }
        Stack<ListNode> stack3 = new Stack<>();
        Integer next = 0;
        while (true)  {
            if (stack1.isEmpty() && stack2.isEmpty()) {
                break;
            }
            ListNode pop1 = new ListNode(0);
            ListNode pop2 = new ListNode(0);
            if (!stack1.isEmpty()) {
                 pop1 = stack1.pop();
            }
            if (!stack2.isEmpty()) {
                pop2 = stack2.pop();
            }
            int add = pop2.val + pop1.val+next;
            next = 0;
            if (add > 9) {
                add = add-10;
                next = 1;
            }
            stack3.push(new ListNode(add));
        }
        if (next > 0 ) {
            stack3.push(new ListNode(next));
        }
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while (!stack3.isEmpty()) {
            p.next = new ListNode(stack3.pop().val);
            p = p.next;
        }
        return head;
    }
}
